package LeetCode;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class LC_056_MergeIntervals {
    public static void main(String[] args) {

    }

    class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    static class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            if (intervals.size() <= 0)
                return intervals;

            //根据interval的start排序
            Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    if (o1.start < o2.start)
                        return -1;
                    else if (o1.start > o2.start)
                        return 1;
                    else
                        return 0;
                }
            });

            //intervals.sort(Comparator.comparingInt(o -> o.start));

            for (int i = 0; i + 1 < intervals.size(); i++) {
                Interval current = intervals.get(i);
                Interval next = intervals.get(i + 1);
                if (current.end >= next.start) {
                    current.end = Math.max(current.end, next.end);
                    intervals.remove(i + 1);
                    i--;
                }
            }

            return intervals;
        }


    }

}
